package lib

//link to 875 410 1231
func init() {
	Probs = append(Probs, Problem{
		Num:         1011,
		Discription: "在k日内运完所有货的情况下，轮船单日载货量的最小值",
		Level:       2,
		Labels: map[string]int{
			"二分查找": 1,
			"单调函数二分":   1,
		},
	})
}

func ShipWithinDays(weights []int, days int) int {
	//在单日最大运货量为cap的情况下，能不能在days日内运完所有货
	canPack := func(cap int) bool {
		curSum := 0
		count := 0
		for _, weight := range weights {
			if curSum+weight > cap {
				count += (curSum + cap - 1) / cap
				curSum = 0
			}
			curSum += weight
		}
		if curSum != 0 {
			count++
		}

		return count <= days
	}

	//最小必要的载货量：每次运一件，最重的那件
	//最多需要的载货量：所有货物的总重量
	left := weights[0]
	right := weights[0]
	for _, weight := range weights {
		left = max(left, weight)
		right += weight
	}

	for left < right {
		mid := left + (right-left)/2
		if canPack(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}